package com.demo.java.OD301_350.OD307;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【找最小数】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146103797
 */
public class OdMain {
    // 移除最小的数字，返回最小的结果数字
    public static ArrayList<Character> removeSmallestDigits(ArrayList<Character> numberList, int digitsToRemove) {
        ArrayList<Character> resultList = new ArrayList<>();
        int insertionIndex = 0;

        // 遍历输入数字列表
        for (char digit : numberList) {
            // 当栈不为空且当前数字小于栈顶元素并且还有需要删除的数字时
            while (!resultList.isEmpty() && resultList.get(resultList.size() - 1) > digit && digitsToRemove > 0) {
                resultList.remove(resultList.size() - 1);  // 弹出栈顶的数字
                digitsToRemove--;  // 减少删除的数量
            }
            resultList.add(digit);  // 将当前数字加入栈中

            // 如果没有数字需要删除了，直接将剩余部分加入
            if (digitsToRemove == 0) {
                resultList.addAll(numberList.subList(insertionIndex + 1, numberList.size()));
                break;
            }
            insertionIndex++;  // 更新插入位置
        }

        // 如果还有数字需要删除，则从栈尾删除
        if (digitsToRemove > 0) {
            resultList.subList(resultList.size() - digitsToRemove, resultList.size()).clear();
        }

        return resultList;
    }

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            String inputNumber = scanner.nextLine();  // 输入的数字字符串
            int digitsToRemove = scanner.nextInt();  // 要删除的数字个数
            ArrayList<Character> numberList = new ArrayList<>();

            // 将输入的数字字符串转换为字符列表
            for (char digit : inputNumber.toCharArray()) {
                numberList.add(digit);
            }

            // 调用方法移除最小的数字
            ArrayList<Character> result = removeSmallestDigits(numberList, digitsToRemove);

            // 将结果字符列表转换为字符串并移除开头的零
            StringBuilder resultBuilder = new StringBuilder();
            for (char digit : result) {
                resultBuilder.append(digit);
            }

            String resultString = resultBuilder.toString().replaceFirst("^0+(?!$)", "");  // 去除前导零
            System.out.println(resultString.isEmpty() ? "0" : resultString);  // 输出结果
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}